public class Test {
    //归并排序
    public static void mergeSort(int[] array){
        mergeSortFunc(array,0,array.length - 1);
    }

    private static void mergeSortFunc(int[] array, int left, int right) {
        if(left >= right){
            return;
        }

        //分开
        int mid = (left + right)/ 2;

        mergeSortFunc(array,left,mid);//左边遍历
        mergeSortFunc(array,mid + 1,right);//右边遍历

        //合并
        merge(array,left,mid,right);

    }

    private static void merge(int[] array,int left,int mid ,int right){
        int s1 = left;
        int s2 = mid + 1;

        int[] tmpArr = new int[right - left +1];
        int k = 0;

        while (s1 <= mid && s2 <= right){
            if(array[s1] < array[s2]){
                tmpArr[k++] = array[s1++];

            }else {
                tmpArr[k++] = array[s2++];

            }
        }

        //防止有一个数组全部放入 另一个还有数据
        while (s1 <= mid){
            tmpArr[k++] = array[s1++];
        }

        while (s2 <= right){
            tmpArr[k++] = array[s2++];
        }

        //tmpArr中的数据一定是这个区间的有序数据
        for (int i = 0; i < tmpArr.length; i++) {
            array[i + left] = tmpArr[i];
        }
    }
    //=========================================================================//
    //计数排序
    public static void countSort(int[] array){
        int maxVal = array[0];
        int minVal = array[0];

        //找出数组中最大值最小值
        for (int i = 0; i < array.length - 1; i++) {
            if(array[i] > maxVal){
                maxVal = array[i];
            }

            if(array[i] < minVal){
                minVal = array[i];
            }
        }

        //根据最大值最小值 确定数组大小
        int[] count = new int[maxVal - minVal];

        //开始计数
        for (int i = 0; i < array.length; i++) {
            count[array[i] - minVal] ++;        //优化用[array[i] - minVal就是得到 个位上的数
        }

        //根据count 将数据写回 原数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0){
                array[index] = i + minVal;//真实的数据的值
                count[i] --;
                index ++;
            }
        }
    }
}
